//--------------------------------------------------------------------------------------------------
//                                                   ___  __  __  __  __  __  __  __    __  __  ___ 
// Copyright 2010, Koert van der Veer.              / __)(  )(  )(  \/  )(  )(  )(  )  (  )(  )/ __)
// Licensed under the Apache License,              ( (__  )(__)(  )    (  )(__)(  )(__  )(__)( \__ \
// version 2.0; ("the License")                     \___)(______)(_/\/\_)(______)(____)(______)(___/

// You may not use this file except in compliance with the License.
// You may obtain a copy of the License at 
//     http://www.apache.org/licenses/LICENSE-2.0 
//
// Unless required by applicable law or agreed to in writing, software distributed under the License
// is distributed on an "AS IS" BASIS,  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
// or implied. See the License for the specific language governing permissions and limitations under
// the License. 
//--------------------------------------------------------------------------------------------------
// This file is part of cumulus,  an memory manager implementation in C++.  Details are discussed in
// my blog,  which can be found at http://ondergetekende.nl.  Comments,  suggestions and bug reports
// are welcome. They can be added as comments at the blog. Be advised that in its current form, this
// code is most likely not production ready; it simply hasn't been tested sufficiently. 
//--------------------------------------------------------------------------------------------------

#pragma once

#include "../Utils/DoublyLinkedList.h"

namespace Cumulus
{

namespace FreeLists
{
	template< unsigned int BinCount, unsigned int BinsPerPower, unsigned int MaxBinSize, bool UseFirstFit >
	class DoublyLinkedPowerDistribution
	{
		CompileTimeAssert< (BinsPerPower & (BinsPerPower-1)) == 0 > BinsPerPower_MustBePowerOfTwo;
		CompileTimeAssert< (BinCount % BinsPerPower) == 0 > BinCount_MustBeMultipleOf_BinsPerPower;

		// The free-list data storage
		struct FreeListEntry
		{
			FreeListEntry* Next;
			FreeListEntry* Previous;
			size_t Size;
		};

		// The actual free-lists
		Utils::DoublyLinkedList<FreeListEntry> FreeLists[ BinCount ];

		typedef typename Utils::DoublyLinkedList<FreeListEntry>::Iterator FreeListIterator;
	public:
		static const size_t MinEntrySize = sizeof( FreeListEntry );
		static const size_t MaxEntrySize = MinEntrySize << (BinCount/BinsPerPower);
		static const bool IsThreadSafe = false;

	private:

		// Calculates a bin for the provided size.
		// Returned values can be larger than the actual number of bins.
		int GetBinForSize( size_t Size )
		{
			static int LogMinSize = IntLog2( MinEntrySize ); 
			static int LogBinsPerPower = IntLog2( BinsPerPower ); 

			// Bins are calculated in two passes: 
			// * First, the base power is calculated, which is just the log2 of the size
			// * Secondly, the first few bits of the size are calculated.
			// These two numbers are combined to form one number.

			int SuperBin = IntLog2( Size );
			int SubBin = (Size >> ( SuperBin - LogBinsPerPower )) & (BinsPerPower-1);

			int Bin = (SuperBin - LogMinSize) * BinsPerPower + SubBin;

			// Prevent negative bins, which can happen if the size was too small.
			return (Bin < 0) ? 0 : Bin;
		}

	public:
		/// Adds a block of memory to the free list
		/// @param Memory	Pointer to the memory to be added to the free list
		/// @param Size		Size of the memory block to be added
		/// @return TRUE if the Memory was added to the free list, FALSE otherwise.
		bool Add( void* Memory, size_t Size )
		{
			// If there's not sufficient bytes to maintain our internals, we can't add
			if( Size < MinEntrySize )
			{
				return false;
			}

			// Calculate where the memory should go.
			int Bin = GetBinForSize( Size );

			if( Bin > BinCount )
			{
				// The block was too large to add to the list
				return false;
			}

			if( FreeLists[ Bin ].GetCount() >= MaxBinSize )
			{
				// The bin was full.
				return false;
			}

			// All is well... Add the entry to the selected bin
			FreeListEntry* Entry = reinterpret_cast<FreeListEntry*>( Memory );
			Entry->Size = Size;
			FreeLists[ Bin ].GetHead().InsertAfter( Entry );

			return true;
		}

		void* Get( size_t& Size )
		{
			// Calculate the range of bins to search for a fitting block
			int MinBin = GetBinForSize( Size );
			int MaxBin = (MinBin + 2 >= BinCount) ? (BinCount - 1)  : (MinBin + 2);

			// Loop over the bins
			for( int Bin = MinBin; Bin < MaxBin; Bin++ )
			{
				// Keep track of the best allocation so far
				FreeListIterator Best = FreeLists[ Bin ].GetHead();

				// Use the maximum value for size_t as a sentinel value
				static const size_t SentinelSize = (size_t)(-1);
				size_t BestSize = SentinelSize; // size_t is unsigned

				// Keep track of the previous free list entry to avoid the O(n) Remove, in favor of
				// the O(1) RemoveNext.
				for( FreeListIterator It = FreeLists[ Bin ].GetHead(); !It.IsAtEnd(); ++It )
				{
					if( It->Size >= Size )
					{
						// We've found a valid item
						size_t Overhead = It->Size - Size;

						if( UseFirstFit || Overhead < 4 )
						{
							// Early out, and return this block
							Size = It->Size;
							return It.Remove();
						}
						else if( It->Size < BestSize ) 
						{
							// We've beaten the previous best...
							BestSize = It->Size;
							Best = It;
						}
					}
				}

				// When we didn't use first fit, we should return the best fit now (if any)
				if( !UseFirstFit && BestSize != SentinelSize )
				{
					Size = BestSize;
					return Best.Remove();
				}
			}

			// We've searched and didn't find. Too bad.
			return NULL;
		}

		class Iterator
		{

			DoublyLinkedPowerDistribution< BinCount, BinsPerPower, MaxBinSize, UseFirstFit>& FreeList;
			FreeListIterator BinIterator;
			int BinIndex;

			void IterateNext()
			{
				if( !BinIterator.IsAtEnd() )
					BinIterator++;

				while( BinIterator.IsAtEnd() && ++BinIndex < BinCount )
				{
					BinIterator = FreeList.FreeLists[BinIndex].GetHead();
				}

				assert( BinIndex == BinCount || !BinIterator.IsAtEnd() );
			}

		public:
			Iterator( DoublyLinkedPowerDistribution< BinCount, BinsPerPower, MaxBinSize, UseFirstFit>& InFreeList )
				: FreeList( InFreeList )
				, BinIterator( )
				, BinIndex( -1 )
			{
				IterateNext();
			}

			bool IsAtEnd()
			{
				return BinIterator.IsAtEnd();
			}

			void* operator*() { return &(*BinIterator); }

			Iterator& operator++() { IterateNext(); }
			Iterator& operator++(int) { IterateNext(); }

			void* Remove()
			{
				void* Result = BinIterator.Remove();
				if( BinIterator.IsAtStart() )
				{
					IterateNext();
				}
				return Result;
			}
		};
	};

}
}